This notebook attempt to study The Riordan Group article, by Shapiro, Getu, Woan and Woodson. It is my first attempt to explain ideas and to find meaning and connections among things. We reference objects and equations explained in the article using their reference numbers in order to have a direct mapping to them.
We start with some SymPy stuff in order to setup the environment:
In [1]:
import sympy
from sympy import *
from sympy.abc import x, n, z, t, y, k
from IPython.display import display, Math, Latex
init_printing() # for nice printing, a-la' TeX
%run '../riordan-group.py'
Let $M$ be an infinite matrix with elements $m_{ji} \in \mathbb{C}$ defined as: $$ M = (m_{ji})_{i,j \geq 0}= \left[ \begin{array}{cccccc} m_{00} & m_{01} & m_{02} & \ldots & m_{0i} & \ldots \\ m_{10} & m_{11} & m_{12} & \ldots & m_{1i} & \ldots \\ m_{20} & m_{21} & m_{22} & \ldots & m_{2i} & \ldots \\ \vdots & \vdots & \vdots & \ddots & \vdots & \\ m_{j0} & m_{j1} & m_{j2} & \ldots & m_{ji} & \ldots \\ \vdots & \vdots & \vdots & & \vdots & \ddots \\ \end{array} \right] $$
Now define $C_i(x)$ as a generating function taking coefficients from $i$-th column: $$ C_i(x) = \sum_{j=0}^{\infty}{m_{ji}x^j} $$
So the following matrix product holds: $ \left[\begin{array}{cccccc} 1 & x & x^2 & \ldots & x^j & \ldots \end{array} \right] M = \left[\begin{array}{cccccc} C_0(x) & C_1(x) & C_2(x) & \ldots & C_i(x)& \ldots \end{array} \right] $
Now assume that $C_i(x)$ can be written as $g(x)f(x)^i$, for all $i \geq 0$ where: $$ g(x) = g_0 + g_1 x + g_2 x^2 + g_3 x^3 +\ldots \\ f(x) = x + f_2 x^2 + f_3 x^3 +\ldots$$
So, there are no requirements on function $g$ while function $f$ has to obeys the following: $$f(0) = 0 \\ \left . \frac{\partial f}{\partial x} \right|_0 = 1$$
Under these assumptions we can rewrite: $ \left[\begin{array}{cccccc} 1 & x & x^2 & \ldots & x^j & \ldots \end{array} \right] M = \left[\begin{array}{cccccc} g(x) & g(x)f(x) & g(x)f(x)^2 & \ldots & g(x)f(x)^i & \ldots \end{array} \right] $
and we call a matrix $M = (g(x), f(x))$ a Riordan matrix.
Now take the product on the right with a vector $\left[\begin{array}{cccccc} a_0 & a_1 & a_2 & \ldots & a_i & \ldots \end{array} \right]^T$: $$ \begin{split} \left[\begin{array}{cccccc} 1 & x & x^2 & \ldots & x^j & \ldots \end{array} \right] M \left[\begin{array}{c} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_i \\ \vdots \end{array} \right] &= a_0 g(x) + a_1 g(x) f(x) + a_2 g(x) f(x)^2 + \ldots \\ &= g(x) \left( a_0 + a_1 f(x) + a_2 f(x)^2 + \ldots \right) \\ &= g(x) A(f(x)) \end{split}$$ where $A(t) = a_0 + a_1 t + a_2 t^2 + \ldots$ is the formal power series of the sequence $(a_0, a_1, a_2, \ldots)$.
Observe that $ g(x) A(f(x))$ can be expanded as a formal power series $b_0 + b_1 x + b_2 x^2 + \ldots$ for some sequence $\{b_n\}_{n \in \mathbb{N}}$ after collecting coefficients for equal powers of $x$: applying $\mathcal{G}$ operator it is possibile to write $\mathcal{G}(\{b_n\}) = g(x) A(f(x))$. Since on the right side there is a product of two separable function, it does follow that the generic term of $\{b_n\}$ is a convolution by properties of $\mathcal{G}$, namely: $$ b_n = \sum_{i=0}^{n}{g_i r_{n-i}}$$ where coefficient $r_j$ depends on both finitely coefficients $a_0, \ldots, a_j$ both on infinitely coefficients $f_2,f_3,\ldots$
Let $M, N$ be two Riordan matrices such that $M = (g(x),f(x))$ and $N = (h(x),l(x))$. In order to study the product $M N$ consider the $i$-th column of matrix $N$, namely coefficients in the formal power series expansion of $h(x)l(x)^i$. By product by vector explanation above, coefficients of $i$-th column of $M N$ are denoted by series expansion of $g(x)h(f(x))l(f(x))^i$, hence repeating the same reasoning for all $i$, it is possible to write: $M N = (g(x)h(f(x)), l(f(x)))$ hence $M N$ is a Riordan matrix too.
In [37]:
def g(x): return 1
def f(x): return x
Latex(Riordan_matrix_latex_code(g, f, x, order=10))
Out[37]:
In this section we'll built the standard Pascal triangle, developing the Riordan matrix $(g(x),f(x))$ that represent a matrix such that row $r$ contains coefficients of $(x + y)^r$, namely ${ {r} \choose {i} }$, for $i \in \{0,\ldots,r\}$.
Since the matrix $$M = \left({ {j} \choose {i} }\right)_{i,j \geq 0}$$ is well known, we proceed in two step in order to define functions $g(x)$ and $f(x)$, starting with the former one. Observe that $g(x)$ is the same as $C_0(x) = 1 + x + x^2 + x^3 + \ldots $, so it is a formal power series, where each coefficient equals 1, hence $g(x)$ is the generating function of the sequence $\{1_n\}_{n\in \mathbb{n}}$, which has a closed form: $$g(x) = \mathcal{G}\{1_n\} = \frac{1}{1-x}$$
Now set for $f(x)$. By definition of Riordan matrix, the expansion of $C_1(x) = g(x)f(x)$ as power series should collect coefficients from the second column, namely the natural numbers. Recall that the generating function of the sequence $\{n\}_{n\in \mathbb{N}}$ is: $$\mathcal{G} \{n\} = \mathcal{G}\{n1_n\} = x\frac{\partial \mathcal{G}\{1_n\}}{\partial x} = \frac{x}{(1-x)^2}$$
Hence the following equation yields $f(x)$: $$ \frac{1}{1-x}f(x) = \frac{x}{(1-x)^2}$$
The above reasoning is implemented with the following code:
In [2]:
def g(x): return 1/(1-x)
def f(x): return x/(1-x)
Latex(Riordan_matrix_latex_code(g, f, x, order=20))
In [17]:
two_var_gen_fun = 1/(1-y*(1+x))
display(series(two_var_gen_fun,(1+x)))
display(series(two_var_gen_fun,y))
for k in range(5): display(series(y**k/(1-y)**(k+1),y,n=10))
In this section we approach a variant of the above triangle, starting to work with a matrix $M = (b_{nj})_{n,j \geq 0}$ where coefficients aren't explicitly defined but obey to the recurrence: $$ b_{n+1,j} = b_{n, j-1} + b_{n, j+1}$$
where $j > 0$. Assume the relation holds for all $n \in \mathbb{N}$ so it is possible to apply the Identity principle: $$ \begin{split} \mathcal{G}\{b_{n+1,j}\} &= \mathcal{G}\{b_{n, j-1} + b_{n, j+1}\} \\ \mathcal{G}\{b_{n+1,j}\} &= \mathcal{G}\{b_{n, j-1}\} + \mathcal{G}\{b_{n, j+1}\} \quad \text{ by linearity of } \mathcal{G} \\ \frac{\mathcal{G}\{b_{n,j}\}-b_{0j}}{x} &= \mathcal{G}\{b_{n, j-1}\} + \mathcal{G}\{b_{n, j+1}\} \quad \text{ by forward translation of } \mathcal{G} \\ C_j(x) &= xC_{j-1}(x) + xC_{j+1}(x) \quad \forall j > 0: b_{0j} = 0 \end{split}$$
Another way to prove the same result, is to observe that $b_{n+1,j}$ is a convolution of the two terms $b_{n,j-1}$ and $b_{n,j+1}$, hence there must exists two functions, say $h_j(x) = h_{0j} + h_{1j} x + h_{2j} x^2 + \ldots$, where coefficient $h_{i,j}= b_{i,j-1} + b_{i,j+1}$ and $l(x) = l_0 + l_1 x + l_2 x^2 + \ldots$, such that: $$\mathcal{G}\left\lbrace\sum_{k=0}^{n+1}{h_{k,j} l_{n+1-k}}\right\rbrace = h_j(x)l(x)$$
Choose $l(x) = x$ because the entire sum should reduce to $b_{n,j-1} + b_{n,j+1}$ which equals $h_{nj}$, hence: $$\begin{split} \mathcal{G}\left\lbrace\sum_{k=0}^{n+1}{h_{k,j} l_{n+1-k}}\right\rbrace &= \mathcal{G}\left\lbrace{h_{n,j} l_{1}}\right\rbrace \\ &=\mathcal{G}\left\lbrace{b_{n,j-1} + b_{n,j+1}}\right\rbrace \\ &=\mathcal{G}\left\lbrace{b_{n,j-1}}\right\rbrace + \mathcal{G}\left\lbrace{b_{n,j+1}}\right\rbrace \\ &= C_{j-1}(x) + C_{j+1}(x)\end{split}$$
It follows that $h_j(x) = C_{j-1}(x) + C_{j+1}(x)$ as obtained in the former derivation.
In [30]:
def g(x): return 1/sqrt(1 -4*x**2)
def f(x): return (1-sqrt(1 -4*x**2))/(2*x)
Latex(Riordan_matrix_latex_code(g, f, x, order=10))
Out[30]:
In [32]:
series(f(x),x,n=20)
Out[32]:
In [12]:
def g(x): return (1-x**2)/(x**2+1)
def f(x): return x/(1+x**2)
Latex(Riordan_matrix_latex_code(g, f, x, order=10))
Out[12]:
In [14]:
series(f(x),x,n=20)
Out[14]:
In [4]:
def g(x): return 1/sqrt(1-2*x-3*x**2)
def f(x): return (1-x-sqrt(1-2*x-3*x**2))/(2*x)
Latex(Riordan_matrix_latex_code(g, f, x, order=10))
Out[4]:
In [7]:
series(f(x),x,n=10)
display(series((3+2*x+x**2)/(1-x), n=10))
In [12]:
def g(x): return Integer(1)
def f(x): return x/(1-x)
for n in range(1,6):
display(series(f(x)**n, n=10))
Latex(Riordan_matrix_latex_code(g, f, x, order=10))
Out[12]:
In [7]:
def d(t): return (1-t)/(1-2*t)
def h(t): return (1+t)/((1-t)*t)
Latex(Riordan_matrix_latex_code(d, h, t, order=10))
Out[7]:
In [3]:
def curious(m): return ((1 + x)**m)*x**(m+1)/(1 -x -x**2)**(m+1)
[display(series(curious(m),n=10)) for m in range(5)]; None
In [6]:
def g(x): return Integer(1)
def f(x): return x*(1+x)
Latex(Riordan_matrix_latex_code(g, f, x, order=10))
Out[6]:
In [20]:
s = series((1-x)**(2*n),x,n=10).subs(n,4)
s, s.coeff(x**5)-s.coeff(x**4)
Out[20]:
In [21]:
series((1+x)**5,x,n=10)
Out[21]:
In [28]:
list(map(display, (series((1/sqrt(1+2*x-3*x**2))*(1+x)**(n-1) *(1+x),x,n=10) for n in range(5))))
print("\n")
list(map(display, (series((1/sqrt(1+2*x-3*x**2))*(1+x)**(n-1),x,n=10) for n in range(5))))
None
In [21]:
def d(x): return 1/(1-x-x**2)
def h(x): return (1-sqrt(1-4*x))/2
Latex(Riordan_matrix_latex_code(d, h, t, order=10))
Out[21]:
In [19]:
Eq(h(t).factor(), series(h(t),n=10))
Out[19]:
In [33]:
one_less_two_powers = x/((1-x)*(1-2*x))
taken_apart = one_less_two_powers.apart()
display(taken_apart)
display(series(1/(1-2*x)))
display(series(1/(x-1)))
series(one_less_two_powers, n=10)
Out[33]:
In [85]:
def autocorrelation_polynomial(x=x,y=y): return (1 + x**2 * y**2 + x**3 * y**2)
def avoiding_pattern_expr(x=x,y=y): return autocorrelation_polynomial(x,y) / ((1-x-y)*autocorrelation_polynomial(x,y) + x**4 * y**2)
display(avoiding_pattern_expr())
display(avoiding_pattern_expr(x,t/x))
for_thm = avoiding_pattern_expr(x,t)
for_thm.series(x,n=2).coeff(x).series()
Out[85]:
In [72]:
# getting the series over *x* means asking for *rows*'s generating functions
x_series = series(avoiding_pattern_expr(), x,n=10)
# get generating function of row 4th, expand it 'column-wise' (over *y*) in order to build row 4th as desired
avoiding_pattern_expr(), x_series.coeff(x**4).series(y,n=10)
Out[72]:
In [91]:
series(1/(1-t),t,n=10)
Out[91]:
In [69]:
# pattern p: 011
def autocorrelation_polynomial(x=x,y=y): return 1
def avoiding_pattern_expr(x=x,y=y): return autocorrelation_polynomial(x,y) / ((1-x-y)*autocorrelation_polynomial(x,y) + x**2 * y**1)
display(avoiding_pattern_expr())
display(avoiding_pattern_expr(x,t/x))
for_thm = avoiding_pattern_expr(x,t/x)
for_thm.series(x,n=2),for_thm.series(t,n=2)
Out[69]:
In [11]:
def R(n,k): return k/(2*(k-n-1))
[display(series(R(n,k),x=n,n=10)) for k in range(10)]
[display(series(R(n,k),x=k,n=10)) for n in range(10)]
display(R(n, k))
In [12]:
def R(n,k): return (k-1)/n
[display(series(R(n,k),x=n,n=10)) for k in range(10)]
[display(series(R(n,k),x=k,n=10)) for n in range(10)]
display(R(n, k))
In [26]:
def f_1(n): return factorial(3*n+1)*factorial(2*n-5)*factorial(n+2)**2
simplify(Sum(f_1(n-k)/f_1(n), (k,0,3)).doit())
Out[26]:
In [4]:
from IPython.display import Math
Math(r'F(k) = \int_{-\infty}^{\infty} f(x) e^{2\pi i k} dx')
Out[4]:
In [52]:
from IPython.display import Latex
Latex(r"""\begin{eqnarray}
\nabla \times \vec{\mathbf{B}} -\, \frac1c\, \frac{\partial\vec{\mathbf{E}}}{\partial t} & = \frac{4\pi}{c}\vec{\mathbf{j}} \\
\nabla \cdot \vec{\mathbf{E}} & = 4 \pi \rho \\
\nabla \times \vec{\mathbf{E}}\, +\, \frac1c\, \frac{\partial\vec{\mathbf{B}}}{\partial t} & = \vec{\mathbf{0}} \\
\nabla \cdot \vec{\mathbf{B}} & = 0
\end{eqnarray}""")
Latex(r"""\[ 4 \]""")
Out[52]:
In [6]:
from IPython.display import display, Math, Latex
display(Math(r'F(k) = \int_{-\infty}^{\infty} f(x) e^{2\pi i k} dx'))